#include "iostream"
#include "vector"
#include "math.h"
using namespace std;


int minimumIncompatibility(vector<int>& nums, int k) {
    int paraCnt=nums.size();
    int subCnt = paraCnt/k;
    int maskCnt=((1<<paraCnt)-1);

    vector<int> dp(1<<paraCnt,-1);
    int frep[1<<paraCnt];
    memset(frep,(1<<paraCnt)*sizeof(int),0);

    for(int mask=1;mask<=maskCnt;++mask){               //枚举大小为subCnt倍数的子集
        int _1_count = __builtin_popcount(mask);
        int temp = mask;
        int min_num = pow(2,sizeof(int)*8-1)-1;
        int max_num = -pow(2,sizeof(int)*8-1)+1;
        memset(frep,(1<<paraCnt)*sizeof(int),0);
        if((_1_count%subCnt)==0){   //
            for(int i=0;i<mask;i++){ //去重
                if(temp&(~1)){
                    frep[i]++;
                    max_num=max(max_num,nums[i]);
                    min_num=min(min_num,nums[i]);
                    if(frep[i]>1)
                        break;
                }
                temp=temp>>1;
            }
            { //计算 不兼容性
                int mult = _1_count/subCnt;
                if(mult==1){
                    dp[mask]=max_num-min_num;
                }
                else{
                    //又要穷举其子 子集 进行状态转移
                    for(int mask2=1;mask2<mask;++mask2){
                        if(__builtin_popcount(mask2)==subCnt){  //选取一个子集
                            if(dp[mask]==-1){
                                dp[mask]=dp[mask^mask2]+dp[mask2];
                            }
                            else{
                                dp[mask]=min(dp[mask],dp[mask^mask2]+dp[mask2]);
                            }
                        }
                    }

                }
            }
        }
    }
    return dp[maskCnt];
}

int main(){
    vector<int> arr(4);
    arr[0]=1;
    arr[1]=2;
    arr[3]=3;
    arr[4]=4;
    cout<<minimumIncompatibility(arr,2);
}